package com.husk.leetcode.dp;

import org.junit.Test;

import java.util.Arrays;

/**
 * <p>
 * 双蛋问题
 * <p>
 * n个鸡蛋，k层楼，哪层楼，鸡蛋会碎，最多要扔多少次
 * </p>
 *
 * @author hushunke@sm.vvip-u.com
 * @since 2021/3/29
 */
public class DoubleEggModel {

    /**
     * N层楼扔2个玻璃珠，大于某个楼层碎，小于不碎，找临界值，最少需要扔几次，记录每次扔的位置
     * <p>
     * dp[n]=min{max(1,1+dp[n-1]), max(2,1+dp[n-2]) ... , max(n-1, 1+dp[1])}
     * dp[1] = 1, n>=1
     * <p>
     * dp[i]=min{max(j,1+dp[i-j])....max(i-j, 1+dp[j])}, i>j, 1<=j<i
     *
     * @param n
     */
    public void glassBead(int n) {
        // 投掷最小次数
        int[] dp = new int[n + 1];

        Arrays.fill(dp, n);
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                int min = Math.max(dp[i - j] + 1, j);
                if (dp[i] > min) {
                    dp[i] = min;
                }
            }
        }
        System.out.println("最少次数" + dp[n]);

        int[] floor = new int[dp[n]];
        floor[0] = dp[n];
        for (int i = 1, inc = dp[n] - 1; i < dp[n]; i++, inc--) {
            floor[i] = floor[i - 1] + inc;
        }
        Arrays.stream(floor).forEach(value -> System.out.print(value + " "));
    }

    @Test
    public void test() {
        this.glassBead(100);
    }

    /**
     * 887. 鸡蛋掉落
     * <p>
     * https://leetcode-cn.com/problems/super-egg-drop/
     * <p>
     * dp[k][n]
     * 从第x楼往下扔鸡蛋的时候：
     * 鸡蛋不碎，dp[k][n-x]
     * 鸡蛋碎，dp[k-1][x-1]
     * dp[k][n] = min(max(dp[k-1][x-1], dp[k][n-x])) + 1, 1<=x<=N
     *
     * @param k 鸡蛋数量
     * @param n 楼层
     * @return
     */
    public int superEggDrop(int k, int n) {
        int[][] dp = new int[k][n];

        return 0;
    }


}
